Álgebra Booleana Diseño Digital Departamento de Ingeniería Electrónica
Introducción
El álgebra booleana, a través de sus postulados y teoremas, es el punto de partida para diseñar e implementar arquitecturas electrónicas digitales, sin importar la tecnología que subyace al diseño; por ello, los interesados en esta área de conocimiento ingenieril deben tener una formación sólida en esta forma de pensamiento lógico.
La tecnología electrónica continúa evolucionando hacia nuevos materiales que permitan una mayor cantidad de dispositivos electrónicos en la menor área posible (grado de integración), a un menor consumo de potencia y mayor velocidad de operación, entre otras cosas. De esta manera, hemos atestiguado desde el simple control de un interruptor de corriente eléctrica hasta los más modernos transistores hechos con nanomateriales, utilizados para el mismo fin: la síntesis o implementación de arquitecturas electrónicas digitales y analógicas. En nuestro caso particular, el álgebra booleana seguirá siendo el fundamento necesario para abordar el diseño electrónico digital.
Tubo vacío
Transistor
Circuito integrado
Intel Puente Sandy 22nm
Evolución de la tecnología electrónica
De esta manera, abordaremos la temática estableciendo los orígenes del álgebra booleana, el conjunto de valores y operadores lógicos que la constituyen, los postulados y teoremas que la definen, las diferentes formas de expresar y manipular una función lógica, y lo más importante, ejemplos que permitan asimilar y practicar la manipulación y simplificación algebraica.
Objetivo
Expresar las funciones lógicas simplificadas a partir de los postulados y teoremas del álgebra booleana para aplicarlas al diseño de sistemas electrónicos digitales.
Álgebra booleana
La siguiente línea del tiempo muestra el desarrollo y consolidación del álgebra booleana; esto ha propiciado su aplicación hasta la actualidad, y seguramente continuará aplicándose en el futuro.
(s. a.) (2014). George Boole [ilustración]. Tomada de https://goo.gl/dJViGB
E. V. Huntington
Definición formal del álgebra booleana (postulados y teoremas)
(s. a.) (2011). Edward Vermilye Huntington [fotografía]. Tomada de http://www.datuopinion.com/edward-vermilye-huntington
C. E. Shannon Álgebra de interruptores
(s. a.) (2010). Claude Shannon [fotografía]. Tomada de https://goo.gl/z3icS7
Definidos en B
Operador binario
Símbolo
OR o +
U o +
AND o •
∩ o •
Diagramas de Venn
Una herramienta útil para visualizar los teoremas y postulados del álgebra booleana, son los diagramas de Venn, considerando los dos operadores binarios: unión o disyunción (OR o +) e intersección o conjunción (AND o •), así como la existencia de la negación o complemento (NOT o B’).
Ejemplos:
Sean dos conjuntos x y y definidos en B.
Para el operador OR:
Universo de valores
1
Para el operador AND:
Universo de valores
2
Para NOT:
Universo de valores
3
Por lo tanto, formalmente los postulados del álgebra booleana:
Al ser axiomas básicos de la estructura algebraica, no requieren demostración.
Postulado 1:
Universo de valores
x = 0 si x ≠ 1 ; x = 1 sí x ≠ 0
Postulado 2:
Elemento identidad
x + 0 = x ; x .1 = x
Postulado 3:
Conmutatividad
x + Y = Y + x ; x .Y = Y . x
Postulado 4:
Distributividad
x . ( Y + Z )= x .Y +x . Z ; x + Y . Z =( x + Y ).( x + Z )
Postulado 5:
Inverso
x + x = 1 ; x . x = 0
Teorema de la dualidad
El teorema de la dualidad expresa lo siguiente:
“Cada expresión algebraica deducida de los postulados del álgebra booleana permanece válida si los operadores y elementos identidad se intercambian”.
Por ejemplo, retomando el postulado 5:
Podemos expresar los teoremas del álgebra booleana:
Teoremas del álgebra booleana
Dual
1
x + x = x
x ∙ x = x
2
x + 1 = 1
x ∙ 0 = 0
Elementos nulos
3
(x)= x
Involución
4
x + (Y + Z) = (x + Y) + Z
x∙(Y∙Z) = (x∙Y)∙Z
Asociatividad
5
(x+Y)= x∙Y
x∙Y= x+Y
D’Morgan
6
x + x∙Y = x
x∙(x + Y) = x
Absorción
7
x∙(x+Y)=x∙Y
x+x ∙Y=x+Y
Auxiliándonos con los diagramas de Venn, podemos demostrar la veracidad de los teoremas. Por ejemplo:
Sea la equivalencia A(B+C) = AB+ AC.
Analicemos las dos partes de la expresión:
A(B+C)
=
AB + AC
¡Ambos casos tienen el mismo resultado!
Finalmente, podemos demostrar los teoremas aplicando los propios postulados del álgebra booleana.
Ejemplo 1:
Demostración de teorema 1
Postulado 1: x + x = x
Multiplicar por 1 no afecta la expresión.
Sustituimos la equivalencia de 1.
Aplicamos la distributividad.
La multiplicación por su negación es igual a cero.
La suma con cero es el propio valor.
Ejemplo 2:
Demostración del teorema 6
x + yx = x x + y ∙ x = x∙1+x∙y Postulado 2: x ∙ 1 = x = x∙(1+y) Postulado 4: x∙(y+z)=x∙y+x∙z = x∙1 Teorema 2: x + 1 = 1 = x l.q.q.d Postulado 2: x ∙ 1 = x
Ejercicio a realizar previamente: Demostrar el teorema 2.
Función lógica y manipulación algebraica
1. A partir del planteamiento de un problema, determinamos las variables de entrada y salida del mismo.
2. Deducimos y expresamos la relación lógica entre variables (las variables de salida dependen de las de entrada).
3. Una de las primeras formas de expresión de esa relación puede ser con una tabla de verdad.
Tabla de verdad (relación entre variables de entrada y salida)
xn-1xn-2… x0
Ym-1Ym-2…Y0
00…00
??...?
00...01
??...?
00…10
??...?
2n-1
??...?
mfunciones de salida Y dependientes de
n variables de entrada x
Una tabla de verdad es una forma canónica para expresar una o varias funciones.
Ejemplo de formas canónicas
Ejemplo de planteamiento del problema y deducción de funciones lógicas en forma canónica
Detecta los valores de entrada 2, 3, 5 y 7 (en binario) colocando un 1 en la salida F.
Todas las formas de expresión de este ejemplo se consideran canónicas, ya que todos los términos que se expresan contienen a todas las variables de entrada.
Reducción por álgebra booleana
¿Para qué reducir una función? Para tener la misma información expresada con menos términos, lo cual representará posteriormente menor cantidad de circuitos electrónicos para su implementación, ofreciendo diversas ventajas. Algunas de éstas son:
Ejemplo:
Sea la función F(abc) = abc + abc + abc + abc.
Factorizando ac y ab
Identificando el inverso
Elemento identidad para un producto
Función simplificada (forma estándar en suma de productos)
Evaluando la función resultante como comprobación:
Recordemos que en una suma lógica, con un solo término que valga 1, el valor de salida es 1, lo cual se observa en la tabla.
Algo para tomar en cuenta
Sea la función F(a,b,c) = abc + abc + abc + abc.
Definidos en B
abc
F
000
1
001
1
010
1
011
1
100
1
101
1
110
1
111
1
Actividad. Identificando las características del álgebra booleana
Ubicar las características del álgebra booleana resulta de gran importancia porque permite desarrollar funciones lógicas indispensables para el diseño de sistemas electrónicos digitales. Es momento de poner a prueba tus conocimientos.
Autoevaluación. Expresando el álgebra booleana en diferentes funciones lógicas
Expresar distintas funciones lógicas por medio de los teoremas y postulados del álgebra booleana resulta significativo ya que, a partir de ellos, puede aplicarse al diseño de sistemas electrónicos digitales.
Fuentes de información
Bibliografía básica
Mota, R. (s. f.). Algebra booleana [19 diapositivas]. México: Autor.
